
// 647.回文子串
class Solution {
public:
    int countSubstrings(string s) {
        // 使用DP来进行解决 
        // 使用二位DP表实现[j,i]表示是否是回文子串
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        int ret = 0;
        for(int i = 0 ; i < n ;i++)
        {
            for(int j = 0 ; j <= i ; j++)
            {
                if(s[i] == s[j] && (i == j || j + 1 == i || dp[j + 1][i - 1]))
                    dp[j][i] = true;
                ret += dp[j][i];
            }
        }
        return ret;
    }
};